package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例 - 最小路径和
        Solution solution1 = new Solution();
        System.out.println("最小路径和:");
        int[][] grid1 = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println("grid=[[1,3,1],[1,5,1],[4,2,1]]: " + solution1.minPathSum(grid1)); // 7
        int[][] grid2 = {{1, 2, 3}, {4, 5, 6}};
        System.out.println("grid=[[1,2,3],[4,5,6]]: " + solution1.minPathSum(grid2)); // 12

        // 测试用例 - 地下城游戏
        Solution2 solution2 = new Solution2();
        System.out.println("\n地下城游戏:");
        int[][] dungeon1 = {{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}};
        System.out.println("dungeon=[[-2,-3,3],[-5,-10,1],[10,30,-5]]: " + solution2.calculateMinimumHP(dungeon1)); // 7
        int[][] dungeon2 = {{0}};
        System.out.println("dungeon=[[0]]: " + solution2.calculateMinimumHP(dungeon2)); // 1
    }

    // 最小路径和
    static class Solution {
        int[][] dp;

        public int minPathSum(int[][] grid) {
            int m = grid.length, n = grid[0].length;
            dp = new int[m + 1][n + 1];

            // 核心：全部初始化为无穷大
            // 原因：这是"选择最小值"问题，0 会被 Math.min 错误选中
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    dp[i][j] = Integer.MAX_VALUE;
                }
            }

            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i == 1 && j == 1) {
                        dp[i][j] = grid[0][0];  // 起点直接赋值
                        continue;
                    }
                    // 当前最小路径和 = 当前格子 + min(上边来, 左边来)
                    dp[i][j] = grid[i - 1][j - 1] + Math.min(dp[i][j - 1], dp[i - 1][j]);
                }
            }

            return dp[m][n];
        }
    }

    // 地下城游戏
    static class Solution2 {
        // 核心逻辑：你当前格子是 Y，下一个格子需要 X 点血
        // 那你进入当前格子前需要：max(1, X - Y)
        int[][] dp;

        public int calculateMinimumHP(int[][] num) {
            int m = num.length, n = num[0].length;
            dp = new int[m + 2][n + 2];  // 多开一行一列给右边和下边

            // 边界初始化为无穷大（不可达区域）
            for (int i = 0; i <= m + 1; i++) {
                for (int j = 0; j <= n + 1; j++) {
                    dp[i][j] = Integer.MAX_VALUE;
                }
            }

            // 终点的右边和下边设为 1
            // 意思：通关后的"虚拟下一步"需要 1 点血（保证终点计算正确）
            dp[m][n + 1] = 1;
            dp[m + 1][n] = 1;

            // 从右下往左上推导
            for (int i = m; i >= 1; i--) {
                for (int j = n; j >= 1; j--) {
                    // 下一步需求：选择右边或下边需求更少的
                    int next = Math.min(dp[i][j + 1], dp[i + 1][j]);
                    // 当前需求 = max(1, 下一步需求 - 当前房间值)
                    dp[i][j] = Math.max(1, next - num[i - 1][j - 1]);
                }
            }

            return dp[1][1];  // 起点需要的血量
        }
    }
}